{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 31.7 The RSA public-key cryptosystem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.7-1\n",
    "\n",
    "> Consider an RSA key set with $p = 11$, $q = 29$, $n = 319$, and $e = 3$. What value of $d$ should be used in the secret key? What is the encryption of the message $M = 100$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\phi(n) = (p - 1) \\cdot (q - 1) = 280$.\n",
    "\n",
    "$d = e^{-1} ~\\text{mod}~ \\phi(n) = 187$.\n",
    "\n",
    "$P(M) = M^e ~\\text{mod}~ n = 254$.\n",
    "\n",
    "$S(C) = C^d ~\\text{mod}~ n = 254^{187} ~\\text{mod}~ n =  100$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.7-2\n",
    "\n",
    "> Prove that if Alice's public exponent $e$ is $3$ and an adversary obtains Alice's secret exponent $d$, where $0 < d < \\phi(n)$, then the adversary can factor Alice's modulus $n$ in time polynomial in the number of bits in $n$. (Although you are not asked to prove it, you may be interested to know that this result remains true even if the condition $e = 3$ is removed. See Miller [255].)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ed \\equiv 1 ~\\text{mod}~ \\phi(n)$\n",
    "\n",
    "$ed - 1 = 3d - 1 = k \\phi(n)$\n",
    "\n",
    "If $p, q < n / 4$, then $\\phi(n) = n - (p + q) + 1 > n - n / 2 + 1 = n / 2 + 1 > n / 2$.\n",
    "\n",
    "$kn / 2 < 3d - 1 < 3d < 3n$, then $k < 6$, then we can solve $3d - 1 = n - p - n / p + 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.7-3 $\\star$\n",
    "\n",
    "> Prove that RSA is multiplicative in the sense that\n",
    "> \n",
    "> $P_A(M_1) P_A(M_2) \\equiv P_A(M_1, M_2) ~(\\text{mod}~n)$.\n",
    "> \n",
    "> Use this fact to prove that if an adversary had a procedure that could efficiently decrypt $1$ percent of messages from $\\mathbb{Z}_n$ encrypted with $P_A$, then he could employ a probabilistic algorithm to decrypt every message encrypted with $P_A$ with high probability."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Multiplicative:\n",
    "$e$ is relatively prime to $n$.\n",
    "\n",
    "Decrypt:\n",
    "In each iteration randomly choose a prime number $m$ that $m$ is relatively prime to $n$, if we can decrypt $m \\cdot M$, then we can return $m^{-1} M$ since $m^{-1} = m^{n - 2}$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
